#ifndef UCT_SEARCH_H
#define UCT_SEARCH_H

#include "Settings.hpp"
/*注意这里UCT的实现是，每个点的增益，表示上一个节点走这一步的增益*/
/*也就是说，如果这个点是COMPUTER(上一步是USER)，同时*/
/*最后COMPUTER赢了，那么这一点的增益应该是0，表示对上一个点而言，这个点不好*/

/*信心树的树节点*/
class UCTNode
{
  public:
    UCTNode();
    UCTNode(UCTNode *parent_, int **board_, int *top_, int M_, int N_, int last_x_, int last_y_, Role role_);
    void allocate();
    ~UCTNode();
    void set_possible_pos();
    void reset(UCTNode *parent_, int **board_, int *top_, int M_, int N_, int last_x_, int last_y_, Role role_);
    void copy_board(int **board_copy);
    void copy_top(int *top_copy);
    friend class UCTSearch;

  protected:
    UCTNode *parent;          //父亲
    vector<UCTNode *> child;  //后代
    vector<int> possible_pos; //可行的落子位置
    int visited_num;
    int **board;
    int *top;
    int M, N;
    double gain;        //收益
    int last_x, last_y; //父亲走的上一步
    State terminal_flag;
    Role role;
};

class UCTSearch
{
    friend class DecisionMaker;

  public:
    UCTSearch(){};
    UCTSearch(int M_, int N_, int noX, int noY);
    ~UCTSearch();

    int search(clock_t start);                                                 //返回最佳的列
    void reset(int M_, int N_, int **board_, int *top_, int no_x_, int no_y_); //重置搜索信息
    void clean();
    int used_node() const { return pool_p; }
    /*辅助函数*/
  protected:
    UCTNode *expand(UCTNode *v);                          //随机寻找一个可行的位置扩展节点
    UCTNode *best_child(UCTNode *p, double coef);         //返回一个最佳子节点
    UCTNode *tree_policy(UCTNode *v);                     //扩展UCT的策略
    double default_policy(UCTNode *v);                    //执行一次模拟
    void back_prop(UCTNode *node_ptr, double delta_gain); //收益回传
    bool is_terminal(UCTNode *v);                         //判断是否到达终点
    void put_chess(int x, int y, int **board, int *top, int chess_number); //走一步棋

    /*Variable*/
  protected:
    int M;    //行数
    int N;    //列数
    int no_x; //禁止下的x
    int no_y; //禁止下的y
    int **board_cache;
    int *top_cache;
    default_random_engine generator;
    uniform_int_distribution<int> dis;
    UCTNode *root;
    /*Memory Pool*/
    UCTNode *node_pool;
    int pool_p;
};

#endif